package com.jat.algorithms.sort;

import java.util.Arrays;

/**
 * @author Jat C C J
 * @description: 插入排序
 * @date 2021-9-289:08
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = {3,1,9,4,5,2};
        insert(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 思路：
     * 一个个排序插入
     * 将第一个数和第二个数排序，然后构成一个有序序列
     * 将第三个数插入进去，构成一个新的有序序列
     * 对第四个数、第五个数直到最后一个数，重复第二步
     *
     *
     * 伪代码：
     * 确定插入次数
     * 设定插入数和已经排好序的最后一个数的位置，insertNum和j=i-1
     * 从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位
     * 将当前数放置到空着的地方，即j+1
     * @param array
     */
    private static void insert(int[] array){
        //插入的次数
        for (int i = 0; i < array.length; i++) {
             if (i==0){
                continue;
            }
             //取当前的数作为需要插入的数，拿着个数和前面已经排好序的数对比，找到插入的位置
            int insertNum = array[i];
             //前面排好序的数组的最后一位
            int j = i -1;
            //如果当前数大于插入的数，而且j大于0
            while (j>=0 && insertNum < array[j]){
                //将值往后移动一位
                array[j+1] = array[j] ;
                j--;
            }
            //将插入的数插入到寻找到的位置，因为循环体里面减1了，所以这里需要加1回来
            array[j+1] = insertNum;
        }
    }
}
